import java.util.ArrayList;

/**
 * @author DCSGO
 * @version 1.0
 * 马踏棋盘算法实现
 */
public class HorseChessBoard {
    public static boolean isFinished;

    public static boolean isRightPosition(int[][] visited, int row, int col) {
        return row >= 0 && col >= 0 &&
                row < visited.length && col < visited[0].length;
    }

    //获取下一步能走的位置
    public static ArrayList<Integer[]> next(int curRow, int curCol, int[][] visited) {
        int row, col;
        ArrayList<Integer[]> positions = new ArrayList<>();

        //右上
        row = curRow - 2;
        col = curCol + 1;
        if (isRightPosition(visited, row, col)) {
            positions.add(new Integer[]{row, col});
        }

        //右中上
        row = curRow - 1;
        col = curCol + 2;
        if (isRightPosition(visited, row, col)) {
            positions.add(new Integer[]{row, col});
        }

        //右中下
        row = curRow + 1;
        col = curCol + 2;
        if (isRightPosition(visited, row, col)) {
            positions.add(new Integer[]{row, col});
        }

        //右下
        row = curRow + 2;
        col = curCol + 1;
        if (isRightPosition(visited, row, col)) {
            positions.add(new Integer[]{row, col});
        }

        //左下
        row = curRow + 2;
        col = curCol - 1;
        if (isRightPosition(visited, row, col)) {
            positions.add(new Integer[]{row, col});
        }

        //左中下
        row = curRow + 1;
        col = curCol - 2;
        if (isRightPosition(visited, row, col)) {
            positions.add(new Integer[]{row, col});
        }

        //左中上
        row = curRow - 1;
        col = curCol - 2;
        if (isRightPosition(visited, row, col)) {
            positions.add(new Integer[]{row, col});
        }

        //左上
        row = curRow - 2;
        col = curCol - 1;
        if (isRightPosition(visited, row, col)) {
            positions.add(new Integer[]{row, col});
        }

        return positions;
    }

    public static void getPath(int curRow, int curCol, int step,
                               int[][] visited, int[][] path) {
        //当前位置标记为已经走过
        visited[curRow][curCol] = 1;
        //记录当前步数到 path
        path[curRow][curCol] = step;

        //所有可移动的位置
        ArrayList<Integer[]> nextPosition = next(curRow, curCol, visited);
        while (!nextPosition.isEmpty()) {
            Integer[] pos = nextPosition.remove(0);
            if (visited[pos[0]][pos[1]] == 0) {//没有走过
                getPath(pos[0], pos[1], step + 1, visited, path);
            }
        }

        if (step == visited.length * visited[0].length || isFinished) {
            isFinished = true;
        } else {//所有可移动的位置都已尝试 但并没有走遍整个棋盘 回溯
            visited[curRow][curCol] = 0;
        }
    }

    public static void printPath(int[][] path) {
        for (int[] rows : path) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    public static void test(int startRow, int startCol, int size) {
        isFinished = false;
        System.out.println("开始位置：" + startRow + " " + startCol);
        int[][] visited = new int[size][size];
        int[][] path = new int[size][size];
        long start = System.currentTimeMillis();
        getPath(startRow, startCol, 1, visited, path);
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start));
        printPath(path);
        System.out.println();
    }

    public static void main(String[] args) {
        test(1, 4, 6);
        test(1, 0, 6);

        /**
         * 开始位置：1 4
         * 耗时：51961
         * 36	21	26	29	8	19
         * 25	30	7	20	1	28
         * 22	35	24	27	18	9
         * 31	6	33	12	15	2
         * 34	23	4	17	10	13
         * 5	32	11	14	3	16
         *
         * 开始位置：1 0
         * 耗时：16928
         * 36	23	2	27	10	21
         * 1	30	9	22	3	28
         * 24	35	26	29	20	11
         * 31	8	33	14	17	4
         * 34	25	6	19	12	15
         * 7	32	13	16	5	18
         *
         * 开始位置：1 4
         *
         * 进程已结束，退出代码为 0
         */
    }
}
